#include<bits/stdc++.h>
using namespace std;
int n,a[200005];
long long dp[2005][2005];
long long dp2[200005][15][15];
inline int read()
{
    char c=getchar();
    while(c<'0'||c>'9')
    c=getchar();
    int ret=0;
    while(c>='0'&&c<='9')
    {
        ret=(ret<<1)+(ret<<3)+c-48;
        c=getchar();
    }
    return ret;
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T=read();
    while(T--)
    {
        n=read();
        int mx=0;
        for(int i=1;i<=n;i++)
        a[i]=read(),mx=max(mx,a[i]);
        memset(dp,0,sizeof(dp));
        if(n>2000)
        {
            if(mx>10)
            {
                printf("0\n");
                continue;
            }
            memset(dp2,-0x3f,sizeof(dp2));
            dp2[1][a[1]][a[1]]=0;
            for(int i=1;i<n;i++)
            {
                for(int j=1;j<=mx;j++)
                for(int k=1;k<=mx;k++)
                {
                    dp2[i+1][a[i+1]][k]=max(dp2[i+1][a[i+1]][k],dp2[i][j][k]+(a[i+1]==j?j:0));
                    dp2[i+1][j][a[i+1]]=max(dp2[i+1][j][a[i+1]],dp2[i][j][k]+(a[i+1]==k?k:0));
                }
            }
            long long ans=0;
            for(int i=1;i<=mx;i++)
            for(int j=1;j<=mx;j++)
            ans=max(ans,dp2[n][i][j]);
            printf("%lld\n",ans);
            continue;
        }
        for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
        {
            if(j>i)
            {
                dp[i][j+1]=max(dp[i][j+1],dp[i][j]+(a[j]==a[j+1]?a[j]:0));
                dp[j+1][j]=max(dp[j+1][j],dp[i][j]+(a[i]==a[j+1]?a[i]:0));
            }
            else if(j<i)
            {
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]+(a[i]==a[i+1]?a[i]:0));
                dp[i][i+1]=max(dp[i][i+1],dp[i][j]+(a[j]==a[i+1]?a[j]:0));
            }
        }
        long long ans=0;
        for(int i=1;i<n;i++)
        ans=max(ans,max(dp[i][n],dp[n][i]));
        printf("%lld\n",ans);
    }
    return 0;
}
